package java学习.leetcode.editor.cn;

import java.util.Arrays;

/**
 * @author 刘世锦
 * 2022-10-21 22:29:05	 当前时间
 */
//给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "abab"
//输出: true
//解释: 可由子串 "ab" 重复两次构成。
// 
//
// 示例 2: 
//
// 
//输入: s = "aba"
//输出: false
// 
//
// 示例 3: 
//
// 
//输入: s = "abcabcabcabc"
//输出: true
//解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
// 
//
// 
//
// 提示： 
//
// 
//
// 
// 1 <= s.length <= 104 
// s 由小写英文字母组成 
// 
// Related Topics 字符串 字符串匹配 
// 👍 805 👎 0

public class 重复的子字符串{
	public static void main(String[] args) {
		Solution solution = new 重复的子字符串().new Solution();

		String  s = "abab";
		System.out.println(solution.repeatedSubstringPattern(s));
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

	/**
	 *  KMP。用处： 在一个串中查找是否出现过另一个串
	 * 1. 求出next数组。
	 * 2. next[n-1] 即为该字符串的最长 前缀、后缀相同字符串的长度
	 * 		前缀、后缀 之差就是 重复的子串。
	 * 3. 子串的长度是否被s整除。
	 */
	public int []  getNext(String s){
		int [] next = new int[s.length()];
		int j = 0;
		next[0] = 0;
		for (int i = 1; i < s.length(); i++) {
			while (j>0&&s.charAt(i)!=s.charAt(j)){
				j = next[j-1];
			}
			if (s.charAt(i)==s.charAt(j)){
				j++;
			}
			next[i] = j;
			// 最后 i++;
		}
		return next;
	}

	/**             0 1 2 3 4 5 6 7 8 9 10 11
	 *          s = a b c a b c a b c a b c
	 *        next  0 0 0 1 2 3 4 5 6 7 8 9
	 *  最长相同前缀： a b c a b c a b c
	 *  最长相同后缀：       a b c a b c a b c
	 *  重复子串：abc： 长度：12-9.
	 */
	public boolean repeatedSubstringPattern(String s) {
		int[] next = getNext(s);
//		System.out.println(Arrays.toString(next));
		int lastlen = next[s.length()-1];// 最长的 前后缀相同子串长度
		int str = s.length()-lastlen;    // 重复出现的子串
		return lastlen!=0&&s.length()%str==0 ;

	}


		public boolean cuowu(String s) {
//    	统计每个字符出现的次数。
		int[] map = new int[26];
		int res = 0;
		for (int i = 0; i <s.length(); i++) {
			 map[s.charAt(i)-'a']++;
				if (map[s.charAt(i)-'a']>1){
//					res = s.substring(i).length();
					res = i; break;
				}
		}
		System.out.println(res);
		return s.length()%res==0;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
